{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #环形链表 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #linked-list #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #链表 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: detectCycle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #环形链表 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 <code>next</code> 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回&nbsp;<code>null</code>。</p>\n",
    "\n",
    "<p>为了表示给定链表中的环，我们使用整数 <code>pos</code> 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 <code>pos</code> 是 <code>-1</code>，则在该链表中没有环。<strong>注意，<code>pos</code> 仅仅是用于标识环的情况，并不会作为参数传递到函数中。</strong></p>\n",
    "\n",
    "<p><strong>说明：</strong>不允许修改给定的链表。</p>\n",
    "\n",
    "<ul>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/07/circularlinkedlist.png\" style=\"height: 97px; width: 300px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [3,2,0,-4], pos = 1\n",
    "<strong>输出：</strong>返回索引为 1 的链表节点\n",
    "<strong>解释：</strong>链表中有一个环，其尾部连接到第二个节点。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/07/circularlinkedlist_test2.png\" style=\"height: 74px; width: 141px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,2], pos = 0\n",
    "<strong>输出：</strong>返回索引为 0 的链表节点\n",
    "<strong>解释：</strong>链表中有一个环，其尾部连接到第一个节点。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/07/circularlinkedlist_test3.png\" style=\"height: 45px; width: 45px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1], pos = -1\n",
    "<strong>输出：</strong>返回 null\n",
    "<strong>解释：</strong>链表中没有环。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表中节点的数目范围在范围 <code>[0, 10<sup>4</sup>]</code> 内</li>\n",
    "\t<li><code>-10<sup>5</sup> &lt;= Node.val &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>pos</code> 的值为 <code>-1</code> 或者链表中的一个有效索引</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>是否可以使用 <code>O(1)</code> 空间解决此题？</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 142&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/linked-list-cycle-ii/\">https://leetcode-cn.com/problems/linked-list-cycle-ii/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [c32eOV](https://leetcode.cn/problems/c32eOV/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [c32eOV](https://leetcode.cn/problems/c32eOV/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,2,0,-4]\\n1', '[1,2]\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "        slow=head\n",
    "        fast=head.next\n",
    "\n",
    "        while fast and fast.next and slow.val!=fast.val:\n",
    "            slow=slow.next\n",
    "            fast=fast.next.next\n",
    "        if not fast or not fast.next:\n",
    "            return None\n",
    "        \n",
    "        pre=head\n",
    "        slow=slow.next\n",
    "\n",
    "        while pre!=slow:\n",
    "            pre=pre.next\n",
    "            slow=slow.next\n",
    "        return slow\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        if not (head and head.next):\n",
    "            return\n",
    "\n",
    "        slow = head\n",
    "        fast = head\n",
    "\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "            if slow == fast:\n",
    "                slow = head\n",
    "                while slow and fast:\n",
    "                    if slow == fast:\n",
    "                        return slow\n",
    "                    slow = slow.next\n",
    "                    fast = fast.next\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        slow=head\n",
    "        fast=head\n",
    "\n",
    "        while fast:\n",
    "            slow=slow.next\n",
    "\n",
    "            if fast.next is None:\n",
    "                return None\n",
    "            fast=fast.next.next\n",
    "            if slow==fast:\n",
    "                pre=head\n",
    "                while pre!=slow:\n",
    "                    pre=pre.next\n",
    "                    slow=slow.next\n",
    "                return pre\n",
    "        return None\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        fast = head\n",
    "        slow = head\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            \n",
    "            if fast == slow:\n",
    "                pos = head\n",
    "                while pos != slow:\n",
    "                    pos = pos.next\n",
    "                    slow = slow.next\n",
    "                return pos\n",
    "            \n",
    "        return \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "        slow = fast = head\n",
    "        while True:\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "            if fast and fast.next:\n",
    "                fast = fast.next\n",
    "            else:\n",
    "                return None\n",
    "            if slow == fast:\n",
    "                break\n",
    "        fast = head\n",
    "        while fast != slow:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        return slow\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        quick = slow = head\n",
    "\n",
    "        while quick and quick.next:\n",
    "            quick = quick.next.next\n",
    "            slow = slow.next\n",
    "            if quick == slow:\n",
    "                ptr = head\n",
    "                while ptr != slow:\n",
    "                    ptr = ptr.next\n",
    "                    slow = slow.next\n",
    "                return ptr\n",
    "        return None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        fast, slow = head, head\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            if fast == slow:\n",
    "                break\n",
    "        if not fast or not fast.next:\n",
    "            return None\n",
    "        slow = head\n",
    "        while slow != fast:\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "        return slow\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        # 链表、双指针\n",
    "        slow, fast = head, head\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            # 快慢指针相遇，说明有环\n",
    "            if fast == slow:\n",
    "                idx1 = fast\n",
    "                idx2 = head\n",
    "                while idx1 != idx2:\n",
    "                    idx1 = idx1.next\n",
    "                    idx2 = idx2.next\n",
    "                return idx1\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        fast = head\n",
    "        slow = head\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            if fast == slow:\n",
    "                slow = head\n",
    "                while fast != slow:\n",
    "                    fast = fast.next\n",
    "                    slow = slow.next\n",
    "                return fast\n",
    "        return None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        fast, slow = head, head\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "\n",
    "            if slow == fast:\n",
    "                break\n",
    "\n",
    "        if not fast or not fast.next:\n",
    "            return None\n",
    "        \n",
    "        slow = head \n",
    "        while slow != fast:\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "        return slow\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        # a, b\n",
    "        # a-b = n*cn\n",
    "        # a = x1 + na*cn\n",
    "        # b = x1 + nb*cn\n",
    "        # x1 + na*cn = nb*cn\n",
    "        prehead = ListNode()\n",
    "        prehead.next = head\n",
    "        counter1, counter2 = 0, 0\n",
    "        fast, slow = prehead, prehead\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            counter1 += 1\n",
    "            counter2 += 2\n",
    "            if fast == slow:\n",
    "                break\n",
    "                \n",
    "        if fast and fast.next:\n",
    "            cur = prehead\n",
    "            while fast != cur:\n",
    "                fast = fast.next\n",
    "                cur = cur.next\n",
    "            return cur\n",
    "        else:\n",
    "            return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        fast = slow = head\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            if fast == slow:\n",
    "                break\n",
    "        if not fast or not fast.next:\n",
    "            return\n",
    "        fast = head\n",
    "        while fast != slow:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        return fast"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        fast,slow=head,head\n",
    "        while fast and fast.next:\n",
    "            fast=fast.next.next\n",
    "            slow=slow.next\n",
    "            if fast==slow:\n",
    "                cur=head\n",
    "                while cur!=slow:\n",
    "                    cur=cur.next\n",
    "                    slow=slow.next\n",
    "                return cur\n",
    "        return None\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        # slow:x+y  fast:x+n(y+z)\n",
    "        # 2(x+y) = x+y+n(y+z)   x = (n-1)(y+z) + z\n",
    "        slow,fast = head,head\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "            if slow == fast:\n",
    "                slow = head #重新定位到头节点\n",
    "                while slow != fast:\n",
    "                    slow = slow.next\n",
    "                    fast = fast.next\n",
    "                return slow\n",
    "        return None   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        slow = fast = head\n",
    "        has_cycle = False  \n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "            if slow == fast:\n",
    "                has_cycle = True\n",
    "                break\n",
    "        if has_cycle is True:\n",
    "            slow = head\n",
    "            while slow != fast:\n",
    "                slow = slow.next\n",
    "                fast = fast.next\n",
    "            return slow  \n",
    "        else:\n",
    "            return None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return None\n",
    "        fast,slow=head,head\n",
    "        while True:\n",
    "            if not (fast and fast.next):\n",
    "                return \n",
    "            slow=slow.next\n",
    "            fast=fast.next.next\n",
    "            if fast==slow:\n",
    "                break\n",
    "        fast=head\n",
    "        while fast!=slow:\n",
    "            fast,slow=fast.next,slow.next\n",
    "        return fast\n",
    "\n",
    "        # fast, slow = head, head\n",
    "        # while True:\n",
    "        #     if not (fast and fast.next): return\n",
    "        #     fast, slow = fast.next.next, slow.next\n",
    "        #     if fast == slow: break\n",
    "        # fast = head\n",
    "        # while fast != slow:\n",
    "        #     fast, slow = fast.next, slow.next\n",
    "        # return fast\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        fast =  slow = head\n",
    "\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "\n",
    "            if fast == slow:\n",
    "                break\n",
    "\n",
    "        if not fast or not fast.next:\n",
    "            return None\n",
    "        \n",
    "        slow = head\n",
    "\n",
    "        while slow != fast:\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "\n",
    "        return slow\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        s, f = head, head\n",
    "        t = 0\n",
    "        while f and f.next:\n",
    "            if f != s or t == 0:\n",
    "                f = f.next.next\n",
    "                s = s.next\n",
    "            else:    \n",
    "                break\n",
    "            t += 1\n",
    "        \n",
    "        if s != f or f is None or f.next is None:\n",
    "            return None\n",
    "        else:\n",
    "            ptr = head\n",
    "            \n",
    "            while s and ptr:\n",
    "                if s != ptr:\n",
    "                    s = s.next\n",
    "                    ptr = ptr.next\n",
    "                else:\n",
    "                    return ptr\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return head\n",
    "        fast, slow = head, head\n",
    "        while fast and fast.next and slow:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            if fast == slow:\n",
    "                break\n",
    "        if not fast or not fast.next or not slow:\n",
    "            return None\n",
    "        q = head\n",
    "        while q != slow:\n",
    "            q = q.next\n",
    "            slow = slow.next\n",
    "        return q\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "\n",
    "       # 设置两个指针，一快一慢，如果两指针能够相遇，说明有环\n",
    "       # 若能相遇：\n",
    "       # 快指针 2t, 慢指针 t,   慢指针： a+ n(b+c) +b =  a+(n+1)b + nc = 2a + 2b\n",
    "       # a = c + (n-1)(b+c)\n",
    "       # 如果无法相遇，返回 -1\n",
    "\n",
    "        fast = head\n",
    "        slow = head\n",
    "\n",
    "\n",
    "        while(fast):\n",
    "            fast = fast.next\n",
    "            if fast and fast.next:\n",
    "                fast = fast.next\n",
    "            else:\n",
    "                return \n",
    "            slow = slow.next\n",
    "            if fast == slow:\n",
    "                break\n",
    "            \n",
    "\n",
    "        ptr = head \n",
    "\n",
    "        while(ptr != slow):\n",
    "\n",
    "            slow = slow.next\n",
    "            ptr = ptr.next\n",
    "        return ptr\n",
    "\n",
    "       \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        # 链表、双指针\n",
    "        slow, fast = head, head\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            if fast == slow:\n",
    "                idx1 = fast\n",
    "                idx2 = head\n",
    "                while idx1 != idx2:\n",
    "                    idx1 = idx1.next\n",
    "                    idx2 = idx2.next\n",
    "                return idx1\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        slow,fast = head, head\n",
    "        while True:\n",
    "            if not (fast and fast.next):\n",
    "                return\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "            if fast == slow:\n",
    "                break\n",
    "        fast = head\n",
    "        while fast!=slow:\n",
    "            fast, slow = fast.next, slow.next\n",
    "        return fast\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        lower = faster = head\n",
    "        flag = True\n",
    "        while lower != faster or flag:\n",
    "            if not faster or not faster.next:\n",
    "                return None\n",
    "            faster = faster.next.next\n",
    "            lower = lower.next\n",
    "            flag = False\n",
    "        while head != lower:\n",
    "            head = head.next\n",
    "            lower = lower.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "\n",
    "        slow, fast = head, head\n",
    "        while True:\n",
    "            if not slow:\n",
    "                return None\n",
    "            slow = slow.next\n",
    "            if not fast:\n",
    "                return None\n",
    "            fast = fast.next\n",
    "            if not fast:\n",
    "                return None\n",
    "            fast = fast.next\n",
    "            if fast == slow:\n",
    "                break\n",
    "        fast = head\n",
    "        while True:\n",
    "            if slow == fast:\n",
    "                break\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "        return fast\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        fast,slow=head,head\n",
    "        while True:\n",
    "            if not (fast and fast.next):return\n",
    "            fast,slow=fast.next.next,slow.next\n",
    "            if fast==slow:break\n",
    "        fast=head\n",
    "        while fast!=slow:\n",
    "            fast,slow=fast.next,slow.next\n",
    "        return fast"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "\"\"\"\n",
    "空间复杂度o(1)\n",
    "不修改链表\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        slow = fast = head\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "            if slow == fast:\n",
    "                point = head\n",
    "                while point != slow:\n",
    "                    point=point.next\n",
    "                    slow = slow.next\n",
    "                return point\n",
    "        return None\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\"\"\"class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        has = set()\n",
    "        p = head\n",
    "        while p:\n",
    "            has.add(p)\n",
    "            p = p.next\n",
    "            if p in has:\n",
    "                return p\n",
    "        return None\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return None\n",
    "        fast = head\n",
    "        slow = head\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            if fast == slow:\n",
    "                break\n",
    "        if fast!=slow:\n",
    "            return None\n",
    "        slow = head\n",
    "        while slow != fast:\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "        return fast\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        slow, fast = head, head\n",
    "        while True:\n",
    "            if not fast or not fast.next:\n",
    "                return None\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "            if slow == fast:\n",
    "                break\n",
    "        fast = head\n",
    "        while slow != fast:\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "        return slow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        if head==None or head.next==None: \n",
    "            return None\n",
    "        slow,fast=head,head\n",
    "        while True:\n",
    "            if fast==None or fast.next==None:\n",
    "                return None\n",
    "            fast=fast.next.next\n",
    "            slow=slow.next\n",
    "            if fast==slow:\n",
    "                break\n",
    "        fast=head\n",
    "        while fast!=slow:\n",
    "            fast=fast.next\n",
    "            slow=slow.next\n",
    "        return slow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        fast = slow = head\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            if fast is slow:break\n",
    "\n",
    "        if not fast or not fast.next:return\n",
    "        fast = head\n",
    "        while fast is not slow:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        return slow\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def detectCycle(self, head):\n",
    "        fast, slow = head, head\n",
    "        while True:\n",
    "            if not (fast and fast.next): return\n",
    "            fast, slow = fast.next.next, slow.next\n",
    "            if fast == slow: break\n",
    "        fast = head\n",
    "        while fast != slow:\n",
    "            fast, slow = fast.next, slow.next\n",
    "        return fast"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        # 快慢指针\n",
    "        fast = slow = head\n",
    "        # 1.fast每次走两步，slow每次走一步，如果有环两者必然会相遇，如果无环fast先遇到None\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "            # 有环且相遇时停止循环\n",
    "            if slow == fast:\n",
    "                break\n",
    "        # 如果fast不是None，则fast一定等于slow\n",
    "        if fast and fast.next:\n",
    "            # fast从头开始\n",
    "            fast = head\n",
    "            # 与slow相遇则是环的入口点\n",
    "            while fast != slow:\n",
    "                fast = fast.next\n",
    "                slow = slow.next\n",
    "            return fast\n",
    "        return None\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        slow = fast = head\n",
    "        while fast and fast.next:\n",
    "            slow, fast = slow.next, fast.next.next\n",
    "            if slow == fast: # 判断有环, 但是相等的节点不一定是环的入口节点\n",
    "                fast = head\n",
    "                while fast != slow:\n",
    "                    slow, fast = slow.next, fast.next\n",
    "                return fast\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        l,r=head,head\n",
    "        # t=ListNode(-1)\n",
    "        # t.next=head\n",
    "        # l=t\n",
    "        # r=head.next\n",
    "        while r and r.next:\n",
    "            \n",
    "            l=l.next\n",
    "            r=r.next.next\n",
    "            if l==r:\n",
    "                break\n",
    "        if not r or not r.next:return None\n",
    "        l=head\n",
    "        while l!=r:\n",
    "            l=l.next\n",
    "            r=r.next\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        slow, fast = head, head\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "            if slow == fast:\n",
    "                break\n",
    "        if not fast or not fast.next:\n",
    "            return \n",
    "        cur = head\n",
    "        while cur != slow:\n",
    "            cur = cur.next\n",
    "            slow = slow.next\n",
    "        return cur\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return None\n",
    "\n",
    "        # 相遇\n",
    "        fast, slow = head.next.next, head.next\n",
    "        while fast and fast.next and fast != slow:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "        if fast != slow:\n",
    "            return None\n",
    "\n",
    "        # 入口\n",
    "        slow = head\n",
    "        while fast != slow:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        return fast"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return\n",
    "        if (not head.next) or (not head.next.next):\n",
    "            return\n",
    "        pa = head.next\n",
    "        pb = head.next.next\n",
    "        while pa != pb:\n",
    "            if pa == None or pb==None or pb.next == None:\n",
    "                return\n",
    "            pa = pa.next\n",
    "            pb = pb.next.next\n",
    "        pa = head\n",
    "        while pa != pb:\n",
    "            pa = pa.next\n",
    "            pb = pb.next\n",
    "        return pa\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        fast = slow = head\n",
    "        while True:\n",
    "            if not fast or not fast.next:return\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            if fast is slow:break\n",
    "        fast = head\n",
    "        while fast is not slow:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        return slow\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        slow, fast = head, head\n",
    "        while fast!=None:\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "            if fast:fast = fast.next\n",
    "            if slow == fast:break\n",
    "        if fast is None:return fast\n",
    "        slow = head\n",
    "        while slow != fast:\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "        return fast\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        fast,slow=head,head\n",
    "        while True:\n",
    "            if not(fast and fast.next):\n",
    "                return\n",
    "            fast,slow=fast.next.next,slow.next\n",
    "            if fast==slow:\n",
    "                break\n",
    "        fast=head\n",
    "        while fast!=slow:\n",
    "            fast,slow=fast.next,slow.next\n",
    "\n",
    "        return fast\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://labuladong.github.io/algo/di-ling-zh-bfe1b/shuang-zhi-0f7cc\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "# step1: 快慢指针相遇，\n",
    "# step2: 慢指针指向head，同步走，再次相遇，就是环起点\n",
    "# 但是该方法会超时\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return None\n",
    "\n",
    "        slow, fast = head, head\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "            if slow == fast:\n",
    "                break # 如果这一步找到相遇点了，break掉了，那肯定还是符合上面while的条件的\n",
    "        \n",
    "        # 这2个，只要有1个不存在，就说明是上面的while循环到头了都没找到slow和fast的相遇点\n",
    "        if not fast or not fast.next:\n",
    "            return None\n",
    "        \n",
    "        slow = head\n",
    "        while fast != slow:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        \n",
    "        return slow\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        slow, fast = head, head\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "            if fast == slow:\n",
    "                fast = head\n",
    "                while fast != slow:\n",
    "                    fast = fast.next\n",
    "                    slow = slow.next\n",
    "                return fast\n",
    "        return None\n",
    "        \n",
    "        \n",
    "        \n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        h = []\n",
    "        p = head\n",
    "        while p != None:\n",
    "            if p in h:\n",
    "                a = 0\n",
    "                pp = head\n",
    "                if h.index(p) == 0:\n",
    "                    return pp\n",
    "                for i in range(h.index(p)):\n",
    "                    a += 1\n",
    "                    pp = pp.next\n",
    "                    if a == h.index(p):\n",
    "                        return pp\n",
    "            h.append(p)\n",
    "            p = p.next\n",
    "        return None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        if not head:return None\n",
    "        fast = slow = head\n",
    "        while 1:\n",
    "            if not fast or not fast.next:return None\n",
    "            fast,slow = fast.next.next,slow.next\n",
    "            if fast==slow:break\n",
    "        fast = head\n",
    "        while fast!=slow:fast,slow=fast.next,slow.next\n",
    "        return fast\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        f = s = head\n",
    "        while f:\n",
    "            if f.next:\n",
    "                f = f.next.next\n",
    "            else:\n",
    "                return None\n",
    "            s = s.next\n",
    "            if s == f:\n",
    "                break\n",
    "        else:\n",
    "            return None\n",
    "        s = head\n",
    "        while s != f:\n",
    "            s, f = s.next, f.next\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        slow,fast = head,head\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "            if slow == fast:\n",
    "                break\n",
    "        print(fast)\n",
    "        if not fast or not fast.next:\n",
    "            return None\n",
    "\n",
    "        p1 = head\n",
    "        p2 = fast\n",
    "        while p1!=p2:\n",
    "            p2 = p2.next\n",
    "            p1 = p1.next\n",
    "        return p1\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        fast, slow = head, head\n",
    "        while True:\n",
    "            if not (fast and fast.next):\n",
    "                return None\n",
    "            slow, fast = slow.next, fast.next.next\n",
    "            if fast == slow:\n",
    "                break\n",
    "        dummy = head\n",
    "        while dummy != fast:\n",
    "            dummy, fast = dummy.next, fast.next\n",
    "        return dummy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        slow, fast = head, head\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "            if slow == fast:\n",
    "                point = head\n",
    "                while point!=slow:\n",
    "                    point = point.next\n",
    "                    slow = slow.next\n",
    "                return point\n",
    "        return None\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        h = []\n",
    "        p = head\n",
    "        while p != None:\n",
    "            if p in h:\n",
    "                a = 0\n",
    "                pp = head\n",
    "                if h.index(p) == 0:\n",
    "                    return pp\n",
    "                for i in range(h.index(p)):\n",
    "                    a += 1\n",
    "                    pp = pp.next\n",
    "                    if a == h.index(p):\n",
    "                        return pp\n",
    "            h.append(p)\n",
    "            p = p.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        def getIntersect(head):\n",
    "            slow, fast = head, head\n",
    "            while fast and fast.next:\n",
    "                slow = slow.next\n",
    "                fast = fast.next.next\n",
    "                if slow == fast:\n",
    "                    return slow\n",
    "            return None\n",
    "        \n",
    "        if not head:\n",
    "            return None\n",
    "        intersect = getIntersect(head)\n",
    "        if not intersect:\n",
    "            return None\n",
    "        \n",
    "        p1, p2 = head, intersect\n",
    "        while p1 != p2:\n",
    "            p1 = p1.next\n",
    "            p2 = p2.next\n",
    "        \n",
    "        return p1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "\n",
    "        m = {}\n",
    "        p = head\n",
    "        while p:\n",
    "            if p in m:\n",
    "                return p\n",
    "            else:\n",
    "                m[p] = 1\n",
    "            p = p.next\n",
    "        return None\n",
    "        \n",
    "        # fp = head\n",
    "        # while fp:\n",
    "        #     if fp.next == fp:\n",
    "        #         return fp\n",
    "        #     sp = head\n",
    "        #     while sp != fp:\n",
    "        #         if fp.next == sp:\n",
    "        #             return sp\n",
    "        #         sp = sp.next\n",
    "        #     fp = fp.next\n",
    "        # return None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://labuladong.github.io/algo/di-ling-zh-bfe1b/shuang-zhi-0f7cc\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "# step1: 快慢指针相遇，\n",
    "# step2: 慢指针指向head，同步走，再次相遇，就是环起点\n",
    "# 但是该方法会超时\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return None\n",
    "\n",
    "        slow, fast = head, head\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "            if slow == fast:\n",
    "                break # 如果这一步找到相遇点了，break掉了，那肯定还是符合上面while的条件的\n",
    "        \n",
    "        # 这2个，只要有1个不存在，就说明是上面的while循环到头了都没找到slow和fast的相遇点\n",
    "        if not fast or not fast.next:\n",
    "            return None\n",
    "        \n",
    "        slow = head\n",
    "        while fast != slow:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        \n",
    "        return slow\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        cur = head \n",
    "        visited = [cur]\n",
    "        while cur:\n",
    "            cur = cur.next\n",
    "            if cur in visited:\n",
    "                return cur\n",
    "            else:\n",
    "                visited.append(cur)\n",
    "        return \n",
    "\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        slow, fast = head, head\n",
    "        while True:\n",
    "            if fast:\n",
    "                fast = fast.next\n",
    "                fast = fast.next if fast else None\n",
    "            else:\n",
    "                return None\n",
    "            slow = slow.next\n",
    "            if slow == None:\n",
    "                return None\n",
    "            if slow == fast:\n",
    "                break\n",
    "        fast = head\n",
    "        while slow != fast:\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "        return slow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "        slow = fast = head\n",
    "\n",
    "        while 1:\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "            if not fast or not fast.next:\n",
    "                return None\n",
    "            else:\n",
    "                fast = fast.next\n",
    "            \n",
    "            if slow == fast:\n",
    "                slow = head\n",
    "\n",
    "                while slow!= fast:\n",
    "                    slow = slow.next\n",
    "                    fast = fast.next\n",
    "                \n",
    "                return slow\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode):\n",
    "        if not head:\n",
    "            return None\n",
    "        fast = head\n",
    "        slow = head\n",
    "        while True:\n",
    "            if fast.next is None or fast.next.next is None:\n",
    "                return None\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            if fast == slow:\n",
    "                break\n",
    "        \n",
    "        fast = head\n",
    "        while fast != slow:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        return fast"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        fast, slow = head, head\n",
    "        while True:\n",
    "            if not (fast and fast.next): return\n",
    "            fast, slow = fast.next.next, slow.next\n",
    "            if fast == slow: break\n",
    "        fast = head\n",
    "        while fast != slow:\n",
    "            fast, slow = fast.next, slow.next\n",
    "        return fast\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        tmp = {}\n",
    "        while head:\n",
    "            if tmp.get(head):\n",
    "                return head\n",
    "            else:\n",
    "                tmp[head] = 1\n",
    "            head = head.next\n",
    "        return None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        slow,fast = head,head\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "            if slow == fast:\n",
    "                break\n",
    "\n",
    "        if not fast or not fast.next:\n",
    "            return None\n",
    "\n",
    "        slow = head\n",
    "        while slow!= fast:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        return slow\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        S  = set()\n",
    "        \n",
    "        start = head\n",
    "        while start:\n",
    "            if start.next == None:\n",
    "                print(start.next)\n",
    "                return None \n",
    "            elif start not in S:\n",
    "                S.add(start)\n",
    "            else:\n",
    "                frist = start\n",
    "                return frist\n",
    "                break\n",
    "            start = start.next\n",
    "        # cheak = head\n",
    "        # pos = 0\n",
    "        # while cheak:\n",
    "        #     if cheak!=frist:\n",
    "        #         cheak = cheak.next\n",
    "        #         pos = pos+1\n",
    "        #     else:\n",
    "        #         return pos"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        fast = slow = head\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            if fast is slow:break\n",
    "        if not fast or not fast.next:return\n",
    "        fast = head\n",
    "        while fast is not slow:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        return slow\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        h = []\n",
    "        p = head\n",
    "        while p != None:\n",
    "            if p in h:\n",
    "                a = 0\n",
    "                pp = head\n",
    "                if h.index(p) == 0:\n",
    "                    return pp\n",
    "                for i in range(h.index(p)):\n",
    "                    a += 1\n",
    "                    pp = pp.next\n",
    "                    if a == h.index(p):\n",
    "                        return pp\n",
    "            h.append(p)\n",
    "            p = p.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        fast = slow = head\n",
    "        while True:\n",
    "            if fast == None or fast.next == None:\n",
    "                return None\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            if fast == slow:\n",
    "                break\n",
    "        slow = head\n",
    "        while fast!=slow:\n",
    "            slow,fast = slow.next,fast.next\n",
    "        return slow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        mp=dict()\n",
    "        while head:\n",
    "            if head in mp:\n",
    "                return head\n",
    "            mp[head]=1\n",
    "            head=head.next\n",
    "        return None\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head):\n",
    "        fast, slow = head, head\n",
    "        while True:\n",
    "            if not (fast and fast.next): return\n",
    "            fast, slow = fast.next.next, slow.next\n",
    "            if fast == slow: break\n",
    "        fast = head\n",
    "        while fast != slow:\n",
    "            fast, slow = fast.next, slow.next\n",
    "        return fast\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        if head is None or head.next is None:\n",
    "            return None\n",
    "        slow = head\n",
    "        fast = head\n",
    "\n",
    "        while True:\n",
    "            if fast is None or fast.next is None:\n",
    "                return None\n",
    "\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "\n",
    "            if fast == slow:\n",
    "                break\n",
    "\n",
    "        fast = head\n",
    "\n",
    "        while slow != fast:\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "\n",
    "        return slow\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        s=set()\n",
    "        p=head\n",
    "        while p!=None:\n",
    "            if p in s:\n",
    "                return p\n",
    "            s.add(p)\n",
    "            p=p.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "\"\"\"\n",
    "空间复杂度o(1)\n",
    "不修改链表\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        has = set()\n",
    "        p = head\n",
    "        while p:\n",
    "            has.add(p)\n",
    "            p = p.next\n",
    "            if p in has:\n",
    "                return p\n",
    "\n",
    "        return None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        hashtable = set()\n",
    "        while head is not None:\n",
    "            if head in hashtable:\n",
    "                return head\n",
    "            hashtable.add(head)\n",
    "            head = head.next\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        mp=dict()\n",
    "        while head:\n",
    "            if head in mp:\n",
    "                return head\n",
    "            mp[head]=1\n",
    "            head=head.next\n",
    "        return None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        nodes = set()\n",
    "        while head:\n",
    "            if head in nodes:\n",
    "                return head\n",
    "            nodes.add(head)\n",
    "            head = head.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        #考虑空链表的情况\n",
    "        if head is None:\n",
    "            return None\n",
    "\n",
    "        p = head\n",
    "        dicts = {}\n",
    "        while p != None:\n",
    "            if p in dicts:\n",
    "                return p\n",
    "            \n",
    "            dicts[p] = 1\n",
    "            p = p.next\n",
    "\n",
    "        return p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        pos = -1\n",
    "        p = head\n",
    "        visited = {}\n",
    "        while p:\n",
    "            if p in visited:\n",
    "                return p\n",
    "            else:\n",
    "                visited[p]=pos\n",
    "            p = p.next\n",
    "            pos+=1\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        # 利用哈希表保存节点，如果节点已存在与哈希表中说明节点就是入环点\n",
    "        dic = set()\n",
    "        while head:\n",
    "            if head not in dic:\n",
    "                dic.add(head)\n",
    "                head = head.next\n",
    "            else:\n",
    "                return head\n",
    "        return None\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def detectCycle(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "        \n",
    "        record = set()\n",
    "        prev = head\n",
    "        record.add(prev)\n",
    "        current = head.next\n",
    "        while current:\n",
    "            if current in record:\n",
    "                return current\n",
    "            record.add(current)\n",
    "            prev = current\n",
    "            current = current.next\n",
    "        \n",
    "        return None"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
